#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_set"
using namespace std;
/*HJJ QQ479287006
 *给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例1:
输入: candidates =[10,1,2,7,6,1,5], target =8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例2:
输入: candidates =[2,5,2,1,2], target =5,
输出:
[
[1,2,2],
[5]
]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//这道题过滤有点问题 总不能遍历查重吧

vector<int> temp;//临时数组
void combinationSumBack(vector<int> &candidates, int target, vector<vector<int>> &ret, int sum, int startIndex) {

    // 2 确定终⽌条件
    if (sum > target)
        return;
    if (target == sum) {

        ret.push_back(temp);
        return;
    }
    //2 确定终⽌条件
    unordered_set<int> uset;//可以建立一个set 来记录同层记录 效率挺低的几乎接近0了
    for (int i = startIndex; i < candidates.size(); ++i) {
        // if(i>startIndex&&candidates[i]==candidates[i-1])
        //     {
        //         continue;
        //     }

        if (uset.find(candidates[i]) != uset.end())
            continue;

        uset.insert(candidates[i]);//不用pop 因为每次都会建立一个

        temp.push_back(candidates[i]);//3 确定单层遍历逻辑 添加到临时数组
        combinationSumBack(candidates, target, ret, sum + candidates[i], i + 1);//这里传入i 从当前情况开始 一般是i+1 不从当前开始
        temp.pop_back();//回归初始环境
    }

}

//1 1 2 5 6 7 10
vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
    vector<vector<int>> ret;

    sort(candidates.begin(), candidates.end());

    combinationSumBack(candidates, target, ret, 0, 0);
    return ret;
}


//同一层去重需要 排序的
//TODO 程序员卡尔给出的答案  这个我觉得自己还得深入理解一下。。要不真的不太行啊
//for (int i = startIndex; i < candidates.size() && sum + candidates[i] <=
//target; i++) {
//// used[i - 1] == true，说明同⼀树⽀candidates[i - 1]使⽤过 这个理解
//// used[i - 1] == false，说明同⼀树层candidates[i - 1]使⽤过
//// 要对同⼀树层使⽤过的元素进⾏跳过
//if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
//continue;
//注意sum + candidates[i] <= target为剪枝操作，在39.组合总和有讲解过！
//C++代码
//        回溯三部曲分析完了，整体C++代码如下：
//}
//sum += candidates[i];
//path.push_back(candidates[i]);
//used[i] = true;  //TODO 原来这里我是不理解的其实 为什么这里设置为true 之后设置为false了又 难道不是相当于没有设置吗（其实这个是向下便利的是一天树枝下的东西）
//backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1：
//这⾥是i+1，每个数字在每个组合中只能使⽤⼀次
//used[i] = false; //TODO 原来这里我是不理解的其实 为什么这里设置为true 之后设置为false了又 其实算这个已经找到了 或者没找到一条树枝 然后 恢复了环境
//sum -= candidates[i];
//path.pop_back();
//}